# June 2016, Dominik Peters
# Go through all weighted majority tournaments for up to 13 voters to check
# whether participation function satisfies pessimistic participation

# Input function depends not only on the weighted tournament,
# but also on the number of voters. So the voting rule's input
# is of form (n, tour), where n is a number of voters,
# and tour is a weighted tournament

import ast
import gc

# readable alternative names
A,B,C,D = 0,1,2,3
string2alt = {"A": A, "B": B, "C": C, "D": D}

# a weighted tournament on 4 alternatives is represented by a 6-tuple;
# each coordinate is the weight of one of the edges, between -n and n;
# edges are in order: ab,ac,ad,bc,bd,cd
# ab = 6 means net 6 voters prefer a to b
votes = [(1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, -1), (1, 1, 1, -1, 1, 1), (1, 1, 1, -1, -1, 1), (1, 1, 1, 1, -1, -1), (1, 1, 1, -1, -1, -1), (-1, 1, 1, 1, 1, 1), (-1, 1, 1, 1, 1, -1), (-1, -1, 1, 1, 1, 1), (-1, -1, -1, 1, 1, 1), (-1, 1, -1, 1, 1, -1), (-1, -1, -1, 1, 1, -1), (1, -1, 1, -1, 1, 1), (1, -1, 1, -1, -1, 1), (-1, -1, 1, -1, 1, 1), (-1, -1, -1, -1, 1, 1), (1, -1, -1, -1, -1, 1), (-1, -1, -1, -1, -1, 1), (1, 1, -1, 1, -1, -1), (1, 1, -1, -1, -1, -1), (-1, 1, -1, 1, -1, -1), (-1, -1, -1, 1, -1, -1), (1, -1, -1, -1, -1, -1), (-1, -1, -1, -1, -1, -1)]

# in a vote given by a tournament, is x ranked above y?
def better(vote,x,y):
    (ab,ac,ad,bc,bd,cd) = vote
    if x == A and y == B:
        return ab > 0
    elif x == A and y == C:
        return ac > 0
    elif x == A and y == D:
        return ad > 0
    elif x == B and y == C:
        return bc > 0
    elif x == B and y == D:
        return bd > 0
    elif x == C and y == D:
        return cd > 0
    elif x == B and y == A:
        return ab < 0
    elif x == C and y == A:
        return ac < 0
    elif x == D and y == A:
        return ad < 0
    elif x == C and y == B:
        return bc < 0
    elif x == D and y == B:
        return bd < 0
    elif x == D and y == C:
        return cd < 0
    else:
        return False

# calculate the condorcet winner of a given tournament
def a_is_winner((ab,ac,ad,bc,bd,cd)):
    return ab > 0 and ac > 0 and ad > 0
def b_is_winner((ab,ac,ad,bc,bd,cd)):
    return ab < 0 and bc > 0 and bd > 0
def c_is_winner((ab,ac,ad,bc,bd,cd)):
    return ac < 0 and bc < 0 and cd > 0
def d_is_winner((ab,ac,ad,bc,bd,cd)):
    return ad < 0 and bd < 0 and cd < 0

# add two tournaments together (component-wise)        
def add(t1,t2):
    return tuple(sum(x) for x in zip(t1, t2))

# does f satisfy pessimistic participation when going from t to t_plus_e?
def participation(t,e,t_plus_e,f):
    for x in [A,B,C,D]:
        # if X is worst, then can't have something even worse (Y)
        for y in [A,B,C,D]:
            if better(e,x,y):
                if x in f(t) and not f(t) & set(z for z in [A,B,C,D] if better(e,x,z)):
                    if y in f(t_plus_e):
                        return False
    return True


print "Reading input file.."
file = open("good_function_pessimistic_13.txt", "r")
function = {}
for i, line in enumerate(file):
    alt = string2alt[line[0]]
    tour = line[line.index('#')+1:]
    tour = ast.literal_eval("("+tour+")")
    if tour not in function:
        function[tour] = {alt}
    else:
        function[tour].add(alt)

def test_function((n, tour)):
    if a_is_winner(tour):
        return {A}
    elif b_is_winner(tour):
        return {B}
    elif c_is_winner(tour):
        return {C}
    elif d_is_winner(tour):
        return {D}
    else:
        return function[(n,tour)]

def check_participation(n,f):
    current_layer = [(1,vote) for vote in votes]
    for layer in range(1,n):
        print "Exploring layer ", layer
        next_layer = set()
        for t in current_layer:
            for e in votes:
                t_plus_e = (layer+1, add(t[1], e))
                next_layer.add(t_plus_e)
                if not participation(t,e,t_plus_e,f):
                    print "Participation Failure Found"
        current_layer = next_layer
        gc.collect()

check_participation(13,test_function)